package com.gxc.graph;

import java.util.*;

/**
 * 面试题 04.01. 节点间通路
 * 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
 */
public class FindWhetherExistsPath {

    public static void main(String[] args) {
        System.out.println(handle(3, new int[][]{
                {0,1},{0,2},{1,2},{1,2}
        }, 0 ,2));
        System.out.println(handle(5, new int[][]{
                {0,1},{0,2},{0,4},{0,4},{0,1},{1,3},{1,4},{1,3},{2,3},{3,4}
        }, 0 ,4));
    }

    public static boolean handle(int n, int[][] graph, int start, int target) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            List<Integer> list = map.getOrDefault(graph[i][0], new ArrayList<>());
            if (list.contains(graph[i][1])) continue;
            list.add(graph[i][1]);
            map.put(graph[i][0], list);
        }
        if (map.get(start) == null) return false;

        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        Set<Integer> set = new HashSet<>();
        set.add(start);
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            if (pop == target) return true;
            set.add(pop);
            List<Integer> list = map.get(pop);
            if (list != null) {
                for (int i = 0; i < list.size(); i++) {
                    if (set.contains(list.get(i))) continue;
                    stack.push(list.get(i));
                }
            }
        }
        return false;
    }

}
